/*
题目：路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，
这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。
https://leetcode.cn/problems/path-sum/
 */
public class HasPathSum {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null)   return false;
        Queue<TreeNode> nodeQueue = new LinkedList<> ();//储存节点队列
        Queue<Integer> valQueue = new LinkedList<> ();//储存节点 值 队列
        nodeQueue.offer(root);
        valQueue.offer(targetSum);

        while (!nodeQueue.isEmpty()) {
            TreeNode curNode = nodeQueue.poll();
            int curVal = valQueue.poll();
            if (curNode.left == null && curNode.right == null && curNode.val == curVal) {
                return true;
            }
            if (curNode.left != null) {
                nodeQueue.offer(curNode.left);
                valQueue.offer(curVal - curNode.val);
            }
            if (curNode.right != null) {
                nodeQueue.offer(curNode.right);
                valQueue.offer(curVal - curNode.val);
            }
        }

        return false;
    }
}